{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Frog Jump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canCross"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #青蛙过河"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。</p>\n",
    "\n",
    "<p>给你石子的位置列表 <code>stones</code>（用单元格序号 <strong>升序</strong> 表示），&nbsp;请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时，&nbsp;青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 <code>1</code> 个单位（即只能从单元格 1 跳至单元格 2 ）。</p>\n",
    "\n",
    "<p>如果青蛙上一步跳跃了&nbsp;<code>k</code><em>&nbsp;</em>个单位，那么它接下来的跳跃距离只能选择为&nbsp;<code>k - 1</code>、<code>k</code><em>&nbsp;</em>或&nbsp;<code>k + 1</code> 个单位。&nbsp;另请注意，青蛙只能向前方（终点的方向）跳跃。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [0,1,3,5,6,8,12,17]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [0,1,2,3,4,8,9,11]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= stones.length &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= stones[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>stones[0] == 0</code></li>\n",
    "\t<li><code>stones</code>&nbsp;按严格升序排列</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [frog-jump](https://leetcode.cn/problems/frog-jump/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [frog-jump](https://leetcode.cn/problems/frog-jump/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,3,5,6,8,12,17]', '[0,1,2,3,4,8,9,11]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1] != 1:\n",
    "            return False\n",
    "        elif len(stones) == 2:\n",
    "            return True\n",
    "\n",
    "        step_log = collections.defaultdict(set)\n",
    "        step_log[1].add(1)\n",
    "        for pos in stones:\n",
    "            if pos not in step_log:\n",
    "                if not step_log:\n",
    "                    return False\n",
    "            else:\n",
    "                for k in step_log.pop(pos):\n",
    "                    for kk in (k - 1, k, k + 1):\n",
    "                        if kk > 0 and pos + kk in stones:\n",
    "                            if pos + kk == stones[-1]:\n",
    "                                return True\n",
    "                            step_log[pos + kk].add(kk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        def lt403(stones):\n",
    "            n=len(stones)\n",
    "            if stones[1]!=1:return False\n",
    "            dp=[[] for _ in range(n)]\n",
    "            dp[1].append(1)\n",
    "            for i in range(1,n-1):\n",
    "                for e in dp[i]:\n",
    "                    for j in range(i+1,n):\n",
    "                        dist=stones[j]-stones[i]\n",
    "                        if dist>e+1:break\n",
    "                        if e+1==dist and e+1 not in dp[j]:dp[j].append(e+1)\n",
    "                        if e==dist and e not in dp[j]:dp[j].append(e)\n",
    "                        if e-1==dist and e-1 not in dp[j]:dp[j].append(e-1)\n",
    "            return dp[-1]!=[]\n",
    "        return lt403(stones)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1] != 1:\n",
    "            return False\n",
    "        for i, s in enumerate(stones):\n",
    "            if s > (i + 1) * i // 2:\n",
    "                return False\n",
    "        maxK, N = stones[-1], len(stones)\n",
    "        dp = [ {} for _ in range(N) ]\n",
    "        dp[1][1] = True\n",
    "        for i in range(2, N):\n",
    "            for j in range(1, i):\n",
    "                step = stones[i] - stones[j]\n",
    "                if step-1 in dp[j] or step in dp[j] or step+1 in dp[j]:\n",
    "                    dp[i][step] = True\n",
    "        # print(dp)\n",
    "        for k, v in dp[-1].items():\n",
    "            if v:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1]!=1:\n",
    "            return False\n",
    "        n=len(stones)\n",
    "        stone_moves=[set() for x in range(n)]\n",
    "        stone_max_moves=[0 for x in range(n)]\n",
    "        stone_moves[1].add(1)\n",
    "        stone_max_moves[1]=1\n",
    "        for i in range(2,n):\n",
    "            for j in range(i-1,0,-1):\n",
    "                if stones[i]-stones[j]-1>stone_max_moves[j]:\n",
    "                    continue\n",
    "                if stones[i]-stones[j] in stone_moves[j]\\\n",
    "                        or stones[i]-stones[j]-1 in stone_moves[j]\\\n",
    "                        or stones[i]-stones[j]+1 in stone_moves[j]:\n",
    "                    stone_moves[i].add(stones[i]-stones[j])\n",
    "                    stone_max_moves[i]=stones[i]-stones[j]\n",
    "        if not stone_moves[n-1]:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        sets = set(stones)\n",
    "        dic = {}\n",
    "        return self.process3(sets, stones[len(stones)-1],  1, 1, dic)\n",
    "\n",
    "    # stones 每个石子的位置\n",
    "    # index，0..index-1可以跳过，index...是否可以过去。限制是上一步跳了s步，下一步只能为s-1,s,s+1\n",
    "    def process3(self, sets, end, pre, cur, dic):\n",
    "        if cur == end:  # 题目中有限制\n",
    "            return True\n",
    "        if cur not in sets:\n",
    "            return False\n",
    "        if cur in dic.keys() and pre in dic[cur].keys():\n",
    "            return dic[cur][pre]\n",
    "        ans = (pre > 1 and self.process3(sets, end, pre - 1, cur + pre - 1, dic)) or \\\n",
    "            self.process3(sets, end, pre, cur + pre, dic) or \\\n",
    "            self.process3(sets, end, pre + 1, cur + pre + 1, dic)\n",
    "        if cur not in dic.keys():\n",
    "            dic[cur] = {}\n",
    "        dic[cur][pre] = ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        d = defaultdict(lambda: set())\n",
    "       \n",
    "        for i in range(stones.__len__()):\n",
    "            if i == 0:\n",
    "                d[1].add(1)\n",
    "            else:\n",
    "                for step in d[stones[i]]:\n",
    "                    for k in range(-1, 2):\n",
    "                        d[stones[i]+max(step+k, 1)].add(max(step+k, 1))\n",
    "\n",
    "        if d[stones[i]].__len__() != 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        start = 0\n",
    "        target = stones[-1]\n",
    "\n",
    "        m = {}\n",
    "        for v in stones:\n",
    "            m[v] = {}\n",
    "\n",
    "\n",
    "        def dfs(start, target, step):\n",
    "            if start == target:\n",
    "                return True\n",
    "            \n",
    "            if step == 0:\n",
    "                return False \n",
    "            \n",
    "            nxt = start + step\n",
    "            if nxt not in m:\n",
    "                return False\n",
    "            if step in m[nxt]:\n",
    "                return m[nxt][step]\n",
    "\n",
    "            ans = dfs(nxt, target, step + 1) \\\n",
    "                or dfs(nxt, target, step) \\\n",
    "                or dfs(nxt, target, step - 1) \n",
    "            \n",
    "            m[nxt][step] = ans\n",
    "            return ans \n",
    "                    \n",
    "\n",
    "        return dfs(start, target, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "\n",
    "        def f(i, k, path):\n",
    "            key = f'{i}-{k}'\n",
    "            if path.get(key, None):\n",
    "                return False\n",
    "            else:\n",
    "                path[key] = True\n",
    "                \n",
    "            for idx in range(i + 1, n):\n",
    "                v = stones[idx] - stones[i]\n",
    "                if v >= k - 1 and v <= k + 1:\n",
    "                    if f(idx, v, path):\n",
    "                        return True\n",
    "                elif v > k + 1:\n",
    "                    break\n",
    "\n",
    "            return i == n - 1\n",
    "            \n",
    "        return f(0, 0, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        self.cache = dict()\n",
    "        return self.cross(stones, 0, 0)\n",
    "\n",
    "    def cross(self, stones, idx, pre_step):\n",
    "        if (idx, pre_step) in self.cache:\n",
    "            return self.cache[(idx, pre_step)]\n",
    "\n",
    "        next_steps = [pre_step - 1, pre_step, pre_step + 1]\n",
    "\n",
    "        for next_step in next_steps:\n",
    "            if next_step <= 0:\n",
    "                continue\n",
    "\n",
    "            next_pos = stones[idx] + next_step\n",
    "            if next_pos == stones[-1]:\n",
    "                self.cache[(idx, pre_step)] = True\n",
    "                return True\n",
    "\n",
    "            next_idx = bisect.bisect_left(stones, next_pos, idx + 1, len(stones))\n",
    "            if next_idx < len(stones) and stones[next_idx] == next_pos:\n",
    "                if self.cross(stones, next_idx, next_step):\n",
    "                    self.cache[(idx, pre_step)] = True\n",
    "                    return True\n",
    "\n",
    "        self.cache[(idx, pre_step)] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        self.cache = dict()\n",
    "        self.stones = set(stones)\n",
    "        self.last_pos = stones[-1]\n",
    "        return self.cross(0, 0)\n",
    "\n",
    "    def cross(self, pre_pos, pre_step):\n",
    "        if (pre_pos, pre_step) in self.cache:\n",
    "            return self.cache[(pre_pos, pre_step)]\n",
    "\n",
    "        next_steps = [pre_step - 1, pre_step, pre_step + 1]\n",
    "\n",
    "        for next_step in next_steps:\n",
    "            if next_step <= 0:\n",
    "                continue\n",
    "\n",
    "            next_pos = pre_pos + next_step\n",
    "            if next_pos == self.last_pos:\n",
    "                self.cache[(pre_pos, pre_step)] = True\n",
    "                return True\n",
    "\n",
    "            if next_pos in self.stones and self.cross(next_pos, next_step):\n",
    "                self.cache[(pre_pos, pre_step)] = True\n",
    "                return True\n",
    "\n",
    "        self.cache[(pre_pos, pre_step)] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        start = 0\n",
    "        target = stones[-1]\n",
    "\n",
    "        m = {}\n",
    "        for v in stones:\n",
    "            m[v] = {}\n",
    "\n",
    "\n",
    "        def dfs(start, target, step):\n",
    "            if start == target:\n",
    "                return True\n",
    "            \n",
    "            if step == 0:\n",
    "                return False \n",
    "            \n",
    "            nxt = start + step\n",
    "            if nxt not in m:\n",
    "                return False\n",
    "            if step in m[nxt]:\n",
    "                return m[nxt][step]\n",
    "\n",
    "            ans = dfs(nxt, target, step) \\\n",
    "                or dfs(nxt, target, step - 1) \\\n",
    "                or dfs(nxt, target, step + 1) \n",
    "            \n",
    "            m[nxt][step] = ans\n",
    "            return ans \n",
    "                    \n",
    "\n",
    "        return dfs(start, target, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "\n",
    "        self.note = {}\n",
    "        for stone in stones:\n",
    "            self.note[stone] = {}\n",
    "        target = stones[-1]\n",
    "        stones = set(stones)\n",
    "        def validNextStone(stone, k):\n",
    "            res = []\n",
    "            for steps in [k-1, k, k+1]:\n",
    "                if steps < 1:\n",
    "                    continue\n",
    "                if stone + steps in stones:\n",
    "                    res.append((stone+steps, steps))\n",
    "            return res\n",
    "\n",
    "        self.ans = False\n",
    "        def dfs(stone, k):\n",
    "            NextStones = validNextStone(stone, k)\n",
    "            if len(NextStones) == 0:\n",
    "                self.note[stone][k] = False\n",
    "            for nextStone, step in NextStones:\n",
    "                if self.ans:\n",
    "                    return\n",
    "                if nextStone == target:\n",
    "                    self.ans = True\n",
    "                    break\n",
    "                if step not in self.note[nextStone]:\n",
    "                    self.note[nextStone][step] = dfs(nextStone, step)\n",
    "            return\n",
    "        if 1 not in stones:\n",
    "            return False\n",
    "        if target == 1:\n",
    "            return True\n",
    "        dfs(1, 1)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "\n",
    "        if stones[1] != 1:\n",
    "            return False\n",
    "        n = len(stones)\n",
    "        \n",
    "        skip_dict = dict()\n",
    "        def skip(pos, s):\n",
    "            key = str(pos)+\"_\"+str(s)\n",
    "            if key in skip_dict:\n",
    "                return skip_dict[key]\n",
    "            if pos == n-1: return True\n",
    "            flag = False\n",
    "            for i in range(pos+1, n):\n",
    "                stance = stones[i] - stones[pos] \n",
    "                if s-1 <= stance:\n",
    "                    if stance <= s+1:\n",
    "                        flag = skip(i, stance)\n",
    "                        if flag: break\n",
    "                    else:\n",
    "                        break\n",
    "            \n",
    "            skip_dict[key] = flag\n",
    "            return flag\n",
    "        return skip(1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        if stones[1] - stones[0] > 1:\n",
    "            return False\n",
    "        # 二分查找\n",
    "        def bitSearch(x: int) -> bool:\n",
    "            l, r = 0, n - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if stones[mid] < x:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            return True if stones[l] == x else False\n",
    "        @cache\n",
    "        def dfs(x: int, k: int):\n",
    "            if x == stones[-1]:\n",
    "                return True\n",
    "            if bitSearch(x + k + 1):\n",
    "                if dfs(x + k + 1, k + 1):\n",
    "                    return True\n",
    "            if bitSearch(x + k):\n",
    "                if dfs(x + k, k):\n",
    "                    return True\n",
    "            if k - 1 > 0 and bitSearch(x + k - 1):\n",
    "                if dfs(x + k - 1, k - 1):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(stones[1], stones[1] - stones[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "\n",
    "        if stones[1] - stones[0] > 1: return False\n",
    "\n",
    "        stonesSet = set(stones) # 变成Set， 加速检索\n",
    "\n",
    "        @functools.lru_cache(None) #加上备忘录，去掉重复计算\n",
    "        def helper(i, step):\n",
    "            # 状态，表示当前是第几块石头，是走几步走过来的。\n",
    "            if i == stones[-1]:\n",
    "                return True\n",
    "\n",
    "            # 选择， 走 step + 1 步， 走 step 步，还是走step - 1 步？，\n",
    "            # 只要往前走的步数有石头（在数组内），就试着可以往前走\n",
    "            if i + step + 1 in stonesSet:\n",
    "                if helper(i + step + 1, step + 1):\n",
    "                    return True\n",
    "\n",
    "            if i + step in stonesSet:\n",
    "                if helper(i+ step, step):\n",
    "                    return True\n",
    "            \n",
    "            if step - 1 > 0 and i + step - 1 in stonesSet:\n",
    "                #这边要检查一下，step -1 要大于0 才走\n",
    "                if helper(i+ step - 1, step -1):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return helper(stones[1], stones[1] - stones[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        @cache\n",
    "        def dfs(i,step):\n",
    "            if i == n-1:\n",
    "                return True\n",
    "            if step == 0 : nxt_stp = [1]\n",
    "            elif step == 1 : nxt_stp = [1,2]\n",
    "            else: nxt_stp = [step-1,step,step+1]\n",
    "\n",
    "            for s in nxt_stp:\n",
    "                idx = bisect_left(stones,stones[i] + s)\n",
    "                if idx < n and stones[idx] == stones[i] + s and dfs(idx,s):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        @cache\n",
    "        def dfs(pos, step):\n",
    "            if pos==stones[-1]: return True\n",
    "            for d in [-1,0,1]:\n",
    "                if step + d >0 and pos + step +d in set(stones):\n",
    "                    if dfs(pos+step+d, step+d):\n",
    "                        return True\n",
    "            return False\n",
    "        pos,step = 0,0\n",
    "        return dfs(pos,step)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        end = stones[-1]\n",
    "        visited = defaultdict(bool)     #记忆化+dfs\n",
    "        stones_set = set(stones)        #为了查找更快\n",
    "\n",
    "        def dfs(start: int, pre_step: int) -> bool:\n",
    "            if start == end:\n",
    "                return True\n",
    "            if (start, pre_step) in visited:\n",
    "                return visited[(start, pre_step)]\n",
    "            for cur_step in (pre_step - 1, pre_step, pre_step + 1):\n",
    "                if cur_step <= 0:    #如果向左了，或者原地了\n",
    "                    continue\n",
    "                nxt_start = start + cur_step #下一步的开始（起跳点）\n",
    "                if nxt_start in stones_set and dfs(nxt_start, cur_step) == True:    #下一步踩在石头上，且后面能到终点\n",
    "                    visited[(start, pre_step)] = True\n",
    "                    return True\n",
    "            visited[(start, pre_step)] = False\n",
    "            return False\n",
    "\n",
    "        return dfs(stones[0], 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1] != 1: return False\n",
    "        n = len(stones)\n",
    "        stones.append(inf)\n",
    "        @cache\n",
    "        def dfs(index: int, stride: int) -> bool:\n",
    "            if index == n - 1: return True\n",
    "            for i in range(max(1, stride - 1), stride + 2):\n",
    "                for k in range(index + 1, n):\n",
    "                    if stones[index] + i > stones[k]: continue\n",
    "                    if stones[index] + i < stones[k]: break\n",
    "                    if dfs(k, i): return True\n",
    "            return False\n",
    "        return dfs(1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        stone = set(stones)\n",
    "        @cache\n",
    "        def check(curr, jump):\n",
    "            if curr == stones[-1]:\n",
    "                return True\n",
    "            if curr not in stone:\n",
    "                return False\n",
    "            for i in range(max(1, jump-1), jump + 2):\n",
    "                if check(curr+i, i):\n",
    "                    return True\n",
    "            return False\n",
    "        return check(0, 0)\n",
    "\n",
    "        # n = len(stones)\n",
    "        # dp = [[False for _ in range(n + 1)] for _ in range(n)]\n",
    "        # if stones[1] != 1:\n",
    "        #     return False\n",
    "        # dp[0][0] = dp[1][1] = True\n",
    "        # #stone_positions = set(stones)  # 使用石头的位置值，而不是索引值\n",
    "        \n",
    "        # for i in range(2, n):\n",
    "        #     for j in range(i - 1, -1, -1):\n",
    "        #         # 检查 stones[j] 而不是 j\n",
    "        #         try:\n",
    "        #             val = stones[j]\n",
    "        #         except:\n",
    "        #             continue\n",
    "        #         diff = stones[i] - stones[j]\n",
    "        #         if diff > i:\n",
    "        #             break\n",
    "                \n",
    "        #         # 使用一个循环来简化状态转移的检查\n",
    "        #         if dp[j][diff - 1] or dp[j][diff] or dp[j][diff + 1]:\n",
    "        #             dp[i][diff] = True\n",
    "\n",
    "\n",
    "        # for j in range(n):\n",
    "        #     if dp[n-1][j]:\n",
    "        #         return True\n",
    "        # return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        y=stones[-1]\n",
    "        stones=set(stones)\n",
    "        g=[]\n",
    "        def dfs(a,b):\n",
    "            if (a,b) in map1:\n",
    "                return \n",
    "            if a==y:\n",
    "                g.append(1)\n",
    "            for i in range(-1,2):\n",
    "                if g:\n",
    "                    return\n",
    "                if i+b>0 and a+i+b in stones:\n",
    "                    dfs(a+i+b,i+b)\n",
    "            map1.add((a,b))\n",
    "        map1=set()\n",
    "        dfs(0,0)\n",
    "        if g:\n",
    "            return (True)\n",
    "        else:\n",
    "            return (False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        stones_set = set(stones)\n",
    "        @cache\n",
    "        def dfs(curr, k):\n",
    "            if curr == stones[-1]:\n",
    "                return True\n",
    "            if curr not in stones_set or k <= 0:\n",
    "                return False\n",
    "            return dfs(curr+k, k-1) or dfs(curr+k, k) or dfs(curr+k, k+1)\n",
    "        \n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    @functools.cache\n",
    "    def jump_result(self, i, step):\n",
    "        # print(i, step)\n",
    "        stones = self.stones\n",
    "        if i == len(stones) - 1:\n",
    "            return True\n",
    "        for j in range(i+1, len(stones)):\n",
    "            if stones[j] - stones[i] == step:\n",
    "                if self.jump_result(j, step) or self.jump_result(j, step - 1) or self.jump_result(j, step + 1):\n",
    "                    return True\n",
    "            if stones[j] - stones[i] > step:\n",
    "                break\n",
    "        \n",
    "        return False\n",
    "        \n",
    "\n",
    "\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        self.stones = stones\n",
    "        return self.jump_result(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        self.max_stone = stones[-1]\n",
    "        self.stones = set(stones)\n",
    "        if stones[1] - stones[0] != 1:\n",
    "            return False\n",
    "        return self._jump(stones[1], 1)\n",
    "    \n",
    "    @cache\n",
    "    def _jump(self, stone, curr_step):\n",
    "        if stone == self.max_stone:\n",
    "            return True\n",
    "        \n",
    "        for next_step in [\n",
    "            curr_step - 1,\n",
    "            curr_step,\n",
    "            curr_step + 1,\n",
    "        ]:\n",
    "            next_pos = next_step + stone\n",
    "            if next_step > 0 and next_pos in self.stones and self._jump(next_pos, next_step):\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.stones=None\n",
    "    @lru_cache(None)\n",
    "    def dfs(self,index,step):\n",
    "        if index==self.stones[-1]:return True\n",
    "        if index not in self.stones:return False\n",
    "        choice=[step-1,step,step+1]\n",
    "        for c in choice:\n",
    "            if c>0 and self.dfs(index+c,c):return True\n",
    "        return False\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        self.stones=stones\n",
    "        return self.dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def canCross(self, stones):\n",
    "        \"\"\"\n",
    "        :type stones: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        self.max_stone = stones[-1]\n",
    "        self.stones = set(stones)\n",
    "        return self._jump(0, 1)\n",
    "    \n",
    "\n",
    "    @cache\n",
    "    def _jump(self, curr, step):\n",
    "        next_pos = curr + step\n",
    "        if next_pos not in self.stones or next_pos > self.max_stone:\n",
    "            return False\n",
    "        if next_pos == self.max_stone:\n",
    "            return True\n",
    "\n",
    "        for next_diff in [-1, 0, 1]:\n",
    "            next_step = step + next_diff\n",
    "            if next_step <= 0:\n",
    "                continue\n",
    "            if self._jump(next_pos, next_step):\n",
    "                return True\n",
    "\n",
    "        return False        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        def solve(i, k):\n",
    "            \"\"\"\n",
    "            跳到第i块石头，步长为k，是否可行？\n",
    "            \"\"\"\n",
    "\n",
    "            nonlocal cache\n",
    "            if i == 0:\n",
    "                if k == 0:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if i < 0:\n",
    "                return False\n",
    "            if k < 1:\n",
    "                return False\n",
    "            if (i, k) in cache:\n",
    "                return cache[(i, k)]\n",
    "            for j in range(i):\n",
    "                distance = stones[i] - stones[j]\n",
    "                if distance != k:\n",
    "                    continue\n",
    "                if solve(j, k - 1) or solve(j, k) or solve(j, k + 1):\n",
    "                    cache[(i, k)] = True\n",
    "                    return True\n",
    "            cache[(i, k)] = False\n",
    "            return False\n",
    "\n",
    "        cache = {}\n",
    "        for k in range(1, len(stones) - 1 + 1):\n",
    "            if solve(len(stones) - 1, k):\n",
    "                # print(len(stones) - 1, k)\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1]!=1:return False\n",
    "        elif len(stones)==2:return True\n",
    "        dp=[[False]*i for i in range(len(stones))]\n",
    "        dp[1][0]=True\n",
    "        for i in range(2,len(stones)):\n",
    "            k0=i-2\n",
    "            for j in range(i-1,0,-1):\n",
    "                d = stones[i]-stones[j]\n",
    "                up=stones[j]-d+1\n",
    "                low = up-2\n",
    "                while k0>=0 and stones[k0]>up:\n",
    "                    k0 -= 1\n",
    "                k=k0\n",
    "                while k>=0 and stones[k]>=low:\n",
    "                    if dp[j][k]:\n",
    "                        if i==len(stones)-1:\n",
    "                            return True\n",
    "                        dp[i][j]=True\n",
    "                        break\n",
    "                    k-=1\n",
    "        # for i,L in enumerate(dp):\n",
    "        #     print(\"%d\\t%s\"%(stones[i],L))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        dp = [[False]*(i+1) for i in range(n)]\n",
    "        dp[0][0] = True\n",
    "        rec = dict()\n",
    "        for i in range(n):\n",
    "            rec[stones[i]] = i\n",
    "        for i in range(1, n):\n",
    "            if stones[i]-stones[i-1] > i:\n",
    "                return False\n",
    "            for j in range(i+1):\n",
    "                if stones[i]-j in rec:\n",
    "                    x = rec[stones[i]-j]\n",
    "                    if 0 <= j-1 <= x:\n",
    "                        dp[i][j] |= dp[x][j-1]\n",
    "                    if j <= x:\n",
    "                        dp[i][j] |= dp[x][j]\n",
    "                    if j+1 <= x:\n",
    "                        dp[i][j] |= dp[x][j+1]\n",
    "        return True in dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        d = {}\n",
    "        for i, j in enumerate(stones):\n",
    "            d[j] = i\n",
    "        @cache\n",
    "        def f(i, k):\n",
    "            # 跳k步到第i个石头是否可行\n",
    "            if k <= 0: return False\n",
    "            if i == 1:\n",
    "                return k == 1 and stones[i] == 1\n",
    "            if stones[i] - k not in d:\n",
    "                return False\n",
    "            j = d[stones[i] - k]\n",
    "            if stones[i] - stones[j] != k: return False \n",
    "            if f(j, k - 1) or f(j, k) or f(j, k + 1): return True\n",
    "            return False\n",
    "        return any(f(n - 1, i) for i in range(1, n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        @cache\n",
    "        def f(i, k):\n",
    "            # 跳k步到第i个石头是否可行\n",
    "            if k <= 0: return False\n",
    "            if i == 1:\n",
    "                return k == 1 and stones[i] == 1\n",
    "            j = bisect_left(stones, stones[i] - k)\n",
    "            if stones[i] - stones[j] != k: return False \n",
    "            if f(j, k - 1) or f(j, k) or f(j, k + 1): return True\n",
    "            return False\n",
    "        return any(f(n - 1, i) for i in range(1, n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        @cache\n",
    "        def f(i, k):\n",
    "            # 跳k步到第i个石头是否可行\n",
    "            if i == 1:\n",
    "                return k == 1 and stones[i] == 1\n",
    "            for j in range(1, i):\n",
    "                if stones[i] - stones[j] != k: continue\n",
    "                if f(j, k - 1) or f(j, k) or f(j, k + 1): return True\n",
    "            return False\n",
    "        return any(f(n - 1, i) for i in range(1, n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "\n",
    "        n = len(stones)\n",
    "        if stones[1]!=1:\n",
    "            return False\n",
    "        \n",
    "        d ={}\n",
    "        for i,x in enumerate(stones):\n",
    "            d[x]=i\n",
    "           \n",
    "        @cache \n",
    "        def dfs(i:int,k:int):\n",
    "            if i >=n-1:\n",
    "                return True\n",
    "            ans = False\n",
    "            x = stones[i]\n",
    "            for j in k-1,k,k+1:\n",
    "                if x+j in d and j >0:\n",
    "                    ans |= dfs(d[x+j],j)\n",
    "            return ans \n",
    "\n",
    "\n",
    "\n",
    "        return dfs(1,1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def jump(self, p: int, k: int):\n",
    "        if p == self.last_place: return True\n",
    "        can_jump = [(p+jl, jl) for jl in (k-1, k, k+1) if jl>0 and p+jl in self.stones]\n",
    "        if not can_jump: return False\n",
    "        return any(self.jump(*i) for i in can_jump)\n",
    "\n",
    "    def canCross(self, stones: List[int]) -> bool:        \n",
    "        self.last_place = stones[-1]\n",
    "        self.stones = set(stones)\n",
    "        return self.jump(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        visited=defaultdict(bool)\n",
    "        n=len(stones)\n",
    "        def dfs(pos,steps):\n",
    "            if pos==stones[-1]:\n",
    "                visited[(pos,steps)]=True\n",
    "                return True\n",
    "            if (pos,steps) in visited:\n",
    "                return visited[(pos,steps)]\n",
    "            if pos not in stones:\n",
    "                visited[(pos,steps)]=False\n",
    "                return False\n",
    "            visited[(pos,steps)]=False\n",
    "            for s in [steps-1,steps,steps+1]:\n",
    "                if s>0:\n",
    "                    visited[(pos,steps)]=visited[(pos,steps)]|dfs(pos+s,s)\n",
    "            return visited[(pos,steps)]\n",
    "\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        visited=defaultdict(bool)\n",
    "        n=len(stones)\n",
    "        def dfs(pos,steps):\n",
    "            if pos==stones[-1]:\n",
    "                visited[(pos,steps)]=True\n",
    "                return True\n",
    "            if (pos,steps) in visited:\n",
    "                return visited[(pos,steps)]\n",
    "            if pos not in stones:\n",
    "                visited[(pos,steps)]=False\n",
    "                return False\n",
    "            visited[(pos,steps)]=False\n",
    "            for s in [steps-1,steps,steps+1]:\n",
    "                if s>0:\n",
    "                    visited[(pos,steps)]=visited[(pos,steps)]|dfs(pos+s,s)\n",
    "            return visited[(pos,steps)]\n",
    "\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: list[int]) -> bool:\n",
    "        \"\"\"\n",
    "        f(i, j)表示青蛙能否跳至第i个石子且上一步跳跃了 k 个单位\n",
    "        f(i, j) = f(x, j - 1)\n",
    "        \"\"\"\n",
    "        n = len(stones)\n",
    "        mem = {}\n",
    "        def f(i, k):\n",
    "            if (i, k) in mem:\n",
    "                return mem[i, k]\n",
    "            if i == n - 1:\n",
    "                res = True\n",
    "            else:\n",
    "                res = False\n",
    "                for t in (k - 1, k, k + 1):\n",
    "                    if t > 0:\n",
    "                        j = bisect_left(stones, stones[i] + t)\n",
    "                        if j != n and stones[j] == stones[i] + t:\n",
    "                            res |= f(j, t)\n",
    "            mem[i, k] = res\n",
    "            return mem[i, k]\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[0]!=0 or stones[1]!=1:\n",
    "            return False\n",
    "        self.memory=dict()\n",
    "        self.stones_dict= {stone:i for i, stone in enumerate(stones)}\n",
    "        def canCrossWithK(stones, K):\n",
    "            if len(stones)==1:\n",
    "                return True\n",
    "            if (len(stones), K) in self.memory.keys():\n",
    "                return self.memory[(len(stones), K)]\n",
    "            choices = [self.findNextStones(stones, i) for i in range(K-1,K+2)]\n",
    "            for choice in choices:\n",
    "                if choice is not None:\n",
    "                    if canCrossWithK(*choice):\n",
    "                        return True\n",
    "            self.memory[(len(stones), K)]=False\n",
    "            return False\n",
    "        return canCrossWithK(stones[1:], 1)\n",
    "    \n",
    "    def findNextStones(self, stones, i):\n",
    "        if i==0:\n",
    "            return None\n",
    "        start=stones[0]\n",
    "        if start+i in self.stones_dict.keys():\n",
    "            return stones[self.stones_dict[start+i]-self.stones_dict[start]:], i\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        stones_s = set(stones)\n",
    "        graph = {0:set([1])}\n",
    "        last_k = {1:set([1])}\n",
    "        \n",
    "        \"\"\"build DAG 石子位置從左至右的有向邊\"\"\"\n",
    "        for stone in stones[1:]:\n",
    "                for k in last_k.get(stone, []):\n",
    "                    for next_k in range(k-1, k+2):\n",
    "                        next_stone = stone + next_k\n",
    "                        if next_k == 0 or (next_stone not in stones_s): continue\n",
    "                        graph.setdefault(stone, set()).add(next_stone)\n",
    "                        last_k.setdefault(next_stone, set()).add(next_k)\n",
    "\n",
    "        \n",
    "        print(graph)\n",
    "        print(last_k)   \n",
    "        \n",
    "        \"\"\"connected problem using dfs\"\"\"\n",
    "        visited = set()\n",
    "        def dfs(u):\n",
    "            visited.add(u)\n",
    "            if u not in graph: return\n",
    "            for v in graph[u]:\n",
    "                if v not in visited:\n",
    "                    dfs(v)\n",
    "\n",
    "        \n",
    "        \"\"\"從起點出發，拜訪連通的節點\"\"\"\n",
    "        dfs(0)\n",
    "\n",
    "        \"\"\"返回終點是否被拜訪\"\"\"\n",
    "        return stones[-1] in visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        length = len(stones)\n",
    "        if length < 1:\n",
    "            return False\n",
    "        result = False\n",
    "        path = set()\n",
    "        def recur(ind, steps):\n",
    "            nonlocal result\n",
    "            if ind == stones[-1]:\n",
    "                result = True\n",
    "                return\n",
    "            elif ind not in stones:\n",
    "                return\n",
    "            for step in steps:\n",
    "                if (ind, step) in path:\n",
    "                    continue\n",
    "                else:\n",
    "                    path.add((ind, step))\n",
    "                recur(ind + step, [step + i for i in range(-1, 2) if i != -step])\n",
    "        recur(stones[0], [1])\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        stoneset = set(stones)\n",
    "        stones_len = len(numpy.array(stones))\n",
    "        stonesdiff = [stones[x] - stones[x-1] for x in range(2,stones_len)]\n",
    "        stonesdiffdiff = [stonesdiff[x] - stonesdiff[x-1] for x in range(2,len(stonesdiff))]\n",
    "        if stones[1]- stones[0] > 1 :\n",
    "            return False\n",
    "        for i in range(0,stones_len):\n",
    "            if round(stones_len*stones_len/2) < stones[i]:\n",
    "                return False\n",
    "        @functools.lru_cache(None) #加上备忘录，去掉重复计算\n",
    "        #for i in range(0,len(stonesdiffdiff)):\n",
    "        #    if stonesdiffdiff[i] >10:\n",
    "        #        return False\n",
    "        def crc(value, step):\n",
    "            if value == stones[-1]:\n",
    "                return True\n",
    "            if value + step - 1 in stoneset and step-1>0:\n",
    "                if crc(value+ step-1, step-1):\n",
    "                    return True\n",
    "            if value + step in stoneset :\n",
    "                if crc(value+ step, step):\n",
    "                    return True\n",
    "            if value + step+1 in stoneset :\n",
    "                if crc(value+ step+1, step+1):\n",
    "                    return True\n",
    "            return False\n",
    "        return crc(stones[1],stones[1]- stones[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        mem = {}\n",
    "\n",
    "        def dp(now, k):\n",
    "            if now == len(stones) - 1:\n",
    "                return True\n",
    "            if (now, k) in mem:\n",
    "                return mem[(now, k)]\n",
    "            left = stones[now+1:]\n",
    "\n",
    "            def test(temp):\n",
    "                if temp <= 0:\n",
    "                    return False\n",
    "\n",
    "                if stones[now] + temp not in left:\n",
    "                    return False\n",
    "                else:\n",
    "                    return dp(stones.index(stones[now] + temp), temp)\n",
    "\n",
    "            if now == 0:\n",
    "                return test(1)\n",
    "\n",
    "            if test(k+1) == True or test(k) == True or test(k-1) == True:\n",
    "                mem[(now, k)] = True\n",
    "                return True\n",
    "\n",
    "            mem[(now, k)] = False\n",
    "            return False\n",
    "        return dp(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        dp=[[False for i in range(1100)]for j in range(1100)]\n",
    "        # dp=np.zeros((1100,1100),dtype=\"bool\")\n",
    "        # for i in range(1100):\n",
    "        #     dp.append([])\n",
    "        #     for j in range(1100):\n",
    "        #         dp[i].append([])\n",
    "        dp[0][1]=True\n",
    "        for i in range(1,len(stones)):\n",
    "            for j in range(i):\n",
    "                step=stones[i]-stones[j]\n",
    "                if(step>=len(stones)):  #会造成执行出错，数组越界\n",
    "                    continue\n",
    "                if(dp[j][step]):   #dp[j][step]之前跳到的地方\n",
    "                    dp[i][step]=True\n",
    "                    dp[i][step-1]=True\n",
    "                    dp[i][step+1]=True\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            if(dp[len(stones)-1][i]==True):\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        import numpy as np\n",
    "        s = set()\n",
    "        def find(l: list, k: int):\n",
    "            length = len(l)\n",
    "            low, high = 0, length - 1\n",
    "            middle = 0\n",
    "            while low < high:\n",
    "                middle = (low + high) // 2\n",
    "                if l[middle] == k:\n",
    "                    return middle\n",
    "                if l[middle] < k:\n",
    "                    low = middle + 1\n",
    "                else:\n",
    "                    high = middle - 1\n",
    "            return middle\n",
    "    # 递归写法\n",
    "        def func(a, b, l):\n",
    "            if (a, l) in s:\n",
    "                return False\n",
    "            temp = l + stones[a]\n",
    "            finded = find(stones, temp)\n",
    "            maybe = [finded-2,finded - 1, finded, finded + 1,finded+2,finded+3]\n",
    "            for i in maybe:\n",
    "            #for i in range(a+1,b):\n",
    "                if i > b:\n",
    "                    break\n",
    "                if i<=a:\n",
    "                    continue\n",
    "                di = stones[i] - stones[a]\n",
    "                if abs(di - l) > 1:\n",
    "                    continue\n",
    "                if i == b:\n",
    "                    return True\n",
    "                if func(i, b, di):\n",
    "                    return True\n",
    "            s.add((a, l))\n",
    "            return False\n",
    "        return func(0,len(stones)-1,0)\n",
    "    # 非递归写法\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        def dfs(cur, k, target):\n",
    "            if cur == target:\n",
    "                return True\n",
    "            state = str(cur) + \",\" + str(k)\n",
    "            if state in memo:\n",
    "                return memo[state]\n",
    "            if cur not in stoneSet:\n",
    "                memo[state] = False\n",
    "                return False\n",
    "            \n",
    "            if cur == 0:\n",
    "                return dfs(1, 1, target)\n",
    "            else:\n",
    "                x = y = z = False\n",
    "                if k - 1 >= 1:\n",
    "                    x = dfs(cur + k - 1, k - 1, target)\n",
    "                if cur + k <= target:\n",
    "                    y = dfs(cur + k, k, target)\n",
    "                if cur + k + 1 <= target:\n",
    "                    z = dfs(cur + k + 1, k + 1, target)\n",
    "                res = x or y or z\n",
    "                memo[state] = res\n",
    "                return res\n",
    "        stoneSet = set(stones)\n",
    "        memo = dict()\n",
    "        return dfs(0, 1, stones[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        stones=numpy.array(stones)\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(c,k):\n",
    "            i=stones[c]\n",
    "            if c== len(stones)-1:\n",
    "                return True\n",
    "            else:\n",
    "                for n,j in enumerate(stones[c+1::]):\n",
    "                    h=j-i\n",
    "                    if h <= k+1 and h >= k-1 :\n",
    "                        if dfs(n+c+1,h)==True:\n",
    "                            return True\n",
    "                    elif h < k-1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return False\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1]-stones[0]>1:return False\n",
    "        st=set(stones)\n",
    "        visited=set()\n",
    "        @cache\n",
    "        def dfs(k,pos):\n",
    "            if pos==stones[-1]:return True\n",
    "            if (k,pos) in visited:return False\n",
    "            visited.add((k,pos))\n",
    "            for i in {-1,0,1}:\n",
    "                if pos+k+i in st and (k+i,pos+k+i) not in visited:\n",
    "                    if dfs(k+i,pos+k+i):\n",
    "                        return True       \n",
    "\n",
    "            return False\n",
    "        ans = dfs(stones[1]-stones[0],stones[1])\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        target = stones[-1]\n",
    "        stones = set(stones)\n",
    "        visit = set()\n",
    "\n",
    "        def dfs(cur, step):\n",
    "            if cur == target:\n",
    "                return True\n",
    "\n",
    "            if (cur, step) in visit:\n",
    "                return False\n",
    "\n",
    "            visit.add((cur,step))\n",
    "\n",
    "            for i in (-1,0,1):\n",
    "                nxt = cur + step + i\n",
    "                if nxt in stones:\n",
    "                    if dfs(nxt, step+i):\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        s = {}\n",
    "        for i in range(len(stones)):\n",
    "            s[stones[i]] = i\n",
    "        dp = [{} for i in range(len(stones))]\n",
    "        dp[0][0] = True\n",
    "        #dp[1][1] = True\n",
    "        for i in range(len(stones)):\n",
    "            k = stones[i]\n",
    "            for j in range(1,i+1):\n",
    "                if k-j in s:\n",
    "                    dp[i][j] = dp[s[k-j]].get(j,False) or dp[s[k-j]].get(j-1,False) or dp[s[k-j]].get(j+1,False)\n",
    "        #print(dp)\n",
    "        for key in dp[len(stones)-1]:\n",
    "            if dp[len(stones)-1].get(key,False):\n",
    "                return True\n",
    "        else:\n",
    "            return False\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        dp = [collections.defaultdict(lambda: False) for _ in range(len(stones))]\n",
    "        dp[0][1] = True \n",
    "        for i in range(1, len(stones)):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                # print(stones[i] - stones[j], dp[j][stones[i] - stones[j]])\n",
    "                if stones[i] - stones[j] <= i and dp[j][stones[i] - stones[j]]:\n",
    "                    # print(i, j)\n",
    "                    dp[i][stones[i] - stones[j]] = True \n",
    "                    dp[i][stones[i] - stones[j] - 1] = True if stones[i] - stones[j] - 1 > 0 else False \n",
    "                    dp[i][stones[i] - stones[j] + 1] = True \n",
    "        # print(dp)\n",
    "        return len(dp[-1]) > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "\n",
    "        m = len(stones)\n",
    "        target = stones[-1]\n",
    "        mark = {}\n",
    "        if stones[:2] != [0,1]:\n",
    "            return False\n",
    "        if len(stones)==2:\n",
    "            return True         \n",
    "        res = 0\n",
    "        def dfs(loc, step):\n",
    "            nonlocal res \n",
    "            if loc==target:\n",
    "                res = 1\n",
    "                return \n",
    "            if (loc, step) in mark:\n",
    "                return \n",
    "            mark[(loc, step)] = True\n",
    "            for i in (step-1, step, step+1):\n",
    "                nloc = loc+i \n",
    "                if nloc in stones:\n",
    "                    dfs(nloc, i)\n",
    "            return False\n",
    "        dfs(1, 1)\n",
    "\n",
    "        return True if res else False\n",
    "            \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def canCross(self, nums: List[int]) -> bool:\n",
    "\n",
    "        if not nums or len(nums) < 1:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        hashdict = defaultdict()\n",
    "        for i, num in enumerate(nums):\n",
    "            hashdict[num] = i\n",
    "        if 1 not in hashdict:\n",
    "            return False\n",
    "        \n",
    "        visited = np.zeros((n, n)) < 0\n",
    "        q = deque()\n",
    "        q.append((1, 1))\n",
    "        visited[1][1] = True\n",
    "        while q:\n",
    "            idx, k = q.popleft()\n",
    "            if idx >= n - 1:\n",
    "                return True\n",
    "            for i in range(-1, 2, 1):\n",
    "                if k + i <= 0:\n",
    "                    continue\n",
    "                next = nums[idx] + k + i\n",
    "                if next in hashdict:\n",
    "                    nIdx = hashdict[next]\n",
    "                    if nIdx >= n-1:\n",
    "                        return True\n",
    "                    nk = k + i\n",
    "                    if not visited[nIdx][nk]:\n",
    "                        visited[nIdx][nk] = True\n",
    "                        q.append((nIdx, nk))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "\n",
    "        # 检查是否超出最大跳跃距离\n",
    "        for i in range(1, n):\n",
    "            if stones[i] - stones[i - 1] > i:\n",
    "                return False\n",
    "\n",
    "        dp = dict()\n",
    "        dp[10001] = True\n",
    "\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                k = stones[i] - stones[j]\n",
    "                if k <= j + 1:\n",
    "                    tmp = j * 10000 + k\n",
    "                    dp[i * 10000 + k] = (dp[tmp - 1] if tmp - 1 in dp else False) or (\n",
    "                        dp[tmp] if tmp in dp else False) or (dp[tmp + 1] if tmp + 1 in dp else False)\n",
    "\n",
    "        tmp = 10000 * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            if tmp + i in dp and dp[tmp + i]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1]-stones[0]>1 : return False\n",
    "        dp=[ [False]*(len(stones)+1) for _ in range(len(stones))]\n",
    "        #dp[i][j] 石头i可通过j步跳过来\n",
    "        dp[1][1]=True\n",
    "        #对每一个石头\n",
    "        for i in range(2,len(stones)):\n",
    "            #查看它前面的所有石头\n",
    "            for j in range(1,i):\n",
    "                #前面的石头到当前石头需要的步数\n",
    "                speed=stones[i]- stones[j]\n",
    "                if speed+1 in range(len(stones)+1):\n",
    "                    dp[i][speed]= dp[j][speed] or  dp[j][speed-1] or dp[j][speed+1]\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            if dp[-1][i]:\n",
    "                return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        if (n==1) | (stones[1]!=1):\n",
    "            return False\n",
    "        max_jump = stones[-1]-stones[0]\n",
    "        memo = [[False]*(n+1) for _ in range(n+1)]\n",
    "        memo[2][1] = True\n",
    "        for i in range(2, n+1):\n",
    "            for j in range(2, i):\n",
    "                jump = stones[i-1]-stones[j-1]\n",
    "                if jump <= j:\n",
    "                    memo[i][jump] = (memo[j][jump-1] | memo[j][jump] | memo[j][jump+1])\n",
    "        return max(memo[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = stones.__len__()\n",
    "        target = stones[-1]\n",
    "        if target == 1:\n",
    "            return True\n",
    "        for idx, i in enumerate(stones):\n",
    "            if i > ((idx + 1) * idx // 2):\n",
    "                return False\n",
    "        dp = [[False] * n for _ in range(n)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(n):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                last_step = stones[i] - stones[j]\n",
    "                if last_step > j + 1:\n",
    "                    break\n",
    "                dp[i][last_step] = dp[j][last_step - 1] or dp[j][last_step] or dp[j][last_step + 1]\n",
    "                if dp[i][last_step] and i == n - 1:\n",
    "                    return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        length, delta = len(stones), (-1, 0, 1)\n",
    "        dp = [[False for _ in range(length)] for _ in range(length)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1, length):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                dis = stones[i] - stones[j]\n",
    "                if dis > j + 1: break\n",
    "                dp[i][dis] = dp[i][dis] or dp[j][dis-1] or dp[j][dis] or dp[j][dis+1]\n",
    "        return bool(sum(dp[-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        # f[i][k] 表示在第i个石子，上一次跳跃距离是k\n",
    "        # f[i][k] = (f[j][k - 1] or f[j][k] or f[j][k + 1])\n",
    "        for i in range(1, n):\n",
    "            if nums[i] - nums[i - 1] > i:\n",
    "                return False\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "        f[0][0] = True\n",
    "        # 当前位置是i\n",
    "        for i in range(1, n):\n",
    "            # 上一个位置是j\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                # 上一次跳跃距离是k - 1, k, k + 1\n",
    "                k = nums[i] - nums[j]\n",
    "                if k > j + 1:\n",
    "                    break\n",
    "                # print(k, j, f[j][k - 1], f[j][k], f[j][k + 1])\n",
    "                f[i][k] = (f[j][k - 1] or f[j][k] or f[j][k + 1])\n",
    "                if i == n - 1 and f[i][k]:\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        # f[i][k] 跳跃能力是k 能否跳到 当前位置i\n",
    "        f = [[False] * (n + 10) for _ in range(n + 10)]\n",
    "        # 起点肯定能到\n",
    "        f[0][0] = True\n",
    "        # 枚举当前坐标i 和 上一坐标k\n",
    "        for i in range(1, n):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                # 则通过当前坐标和上一坐标可以求出跳到i的跳跃能力需要是k\n",
    "                k = nums[i] - nums[j]\n",
    "                # 在坐标j处 跳跃能力最大时j+1 \n",
    "                # 比如：j=0 则最远能跳到1\n",
    "                # j=1 则最远能跳到2\n",
    "                # j=2 则最远能跳到3\n",
    "                # 所以如果j处最大跳跃能力都小于需要的能力k比不可能调过来\n",
    "                if k > j + 1:\n",
    "                    break\n",
    "                # 从j跳到i需要能力k 则从j的上一坐标跳到j 可用的能力就是k-1，k，k+1\n",
    "                f[i][k] = (f[j][k - 1] or f[j][k] or f[j][k + 1])\n",
    "                if i == n - 1 and f[i][k]:\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones) -> bool:\n",
    "        \"\"\"\n",
    "        深度遍历\n",
    "        \"\"\"\n",
    "        n = len(stones)\n",
    "        stones_dict = dict()\n",
    "        for i, stone in enumerate(stones):\n",
    "            stones_dict[stone] = i\n",
    "        self.memo = [[-1] * n for _ in range(n)]\n",
    "        if stones[1] > 1:\n",
    "            return False\n",
    "        return self.dfs(stones, stones_dict, 1, 1)\n",
    "\n",
    "    def dfs(self, stones, stones_dict, i, k):\n",
    "        val = stones[i]\n",
    "        if val + k - 1 <= stones[-1] <= val + k + 1:\n",
    "            return True\n",
    "        \n",
    "        if self.memo[i][k] != -1:\n",
    "            return self.memo[i][k]\n",
    "        # k - 1\n",
    "        res = False\n",
    "        if k > 1 and val + k - 1 in stones_dict:\n",
    "            res = res or self.dfs(stones, stones_dict, stones_dict[val+k-1], k-1)\n",
    "        if val + k in stones_dict:\n",
    "            res = res or self.dfs(stones, stones_dict, stones_dict[val+k], k)\n",
    "        if val + k + 1 in stones_dict:\n",
    "            res = res or  self.dfs(stones, stones_dict, stones_dict[val+k+1], k+1)\n",
    "        # if k < len(stones):\n",
    "        self.memo[i][k] = res\n",
    "        return res\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    runner = Solution()\n",
    "    print(runner.canCross([0,1,3,5,6,8,12,17]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        self.flag = {}\n",
    "        self.position = {}\n",
    "        for i in range(len(stones)):\n",
    "            self.position[stones[i]] = i\n",
    "        def compute(stones, index, step):\n",
    "            if index == len(stones) - 1:\n",
    "                return True\n",
    "            elif (index, step) in self.flag:\n",
    "                return self.flag[(index, step)]\n",
    "            else:\n",
    "                re = False\n",
    "                if stones[index] + step in self.position:\n",
    "                    re = re | compute(stones, self.position[stones[index]+step], step)\n",
    "                if index > 0 and stones[index] + step + 1 in self.position:\n",
    "                    re = re|compute(stones, self.position[stones[index]+step+1], step+1)\n",
    "                if step > 1 and stones[index] + step-1 in self.position:\n",
    "                    re=re|compute(stones, self.position[stones[index]+step-1],step-1)\n",
    "                self.flag[(index, step)] = re\n",
    "                return re\n",
    "        return compute(stones, 0, 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        f[i][j]表示青蛙落在第i块石子，且上一步跳跃了 k 个单位\n",
    "        stones[i] + k\n",
    "        \"\"\"\n",
    "        n = len(stones)\n",
    "        mp = {d: i for i, d in enumerate(stones)}\n",
    "        mem = {}\n",
    "        def f(i, k):\n",
    "            if (i, k) not in mem:\n",
    "                if i == n - 1:\n",
    "                    res = True\n",
    "                else:\n",
    "                    t1 = t2 = t3 = False\n",
    "                    if k > 1 and stones[i] + k - 1 in mp:\n",
    "                        t1 = f(mp[stones[i] + k - 1], k - 1) \n",
    "                    if k > 0 and stones[i] + k in mp:\n",
    "                        t2 = f(mp[stones[i] + k], k) \n",
    "                    if k > -1 and stones[i] + k + 1 in mp:\n",
    "                        t3 = f(mp[stones[i] + k + 1], k + 1) \n",
    "                    res = t1 or t2 or t3\n",
    "                mem[i, k] = res\n",
    "            return mem[i, k]\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dp(self, x, y):\n",
    "        if y >= self.sz:\n",
    "            return 0\n",
    "            \n",
    "        if self.f[x][y] != -1:\n",
    "            return self.f[x][y]\n",
    "        \n",
    "        self.f[x][y] = 0\n",
    "        for step in range(max(1, y-1), y+2):\n",
    "            z = self.stones[x] - step\n",
    "            if z in self.mp:\n",
    "                idx = self.mp[z]\n",
    "                if self.dp(idx, step) == 1:\n",
    "                    self.f[x][y] = 1\n",
    "                    break\n",
    "\n",
    "        return self.f[x][y]\n",
    "\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        self.sz = len(stones)\n",
    "        self.stones = stones\n",
    "        self.mp = {}\n",
    "        self.f = [[-1] * self.sz for _ in range(self.sz)]\n",
    "        self.f[0][1] = 1\n",
    "        \n",
    "        for idx, st in enumerate(stones):\n",
    "            self.mp[st] = idx\n",
    "\n",
    "        for idx in range(self.sz):\n",
    "            if self.dp(self.sz-1, idx):\n",
    "                return True\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        d = {}\n",
    "        n = len(stones)\n",
    "        for i in range(n):\n",
    "            d[stones[i]] = i\n",
    "        if stones[1] != 1:\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i, k):\n",
    "            if i == n-1:\n",
    "                return True\n",
    "            if k == 0:\n",
    "                return False\n",
    "            cur = stones[i]\n",
    "            ans = False\n",
    "            if cur+k-1 in d:\n",
    "                ans |= dfs(d[cur+k-1], k-1)\n",
    "            if cur+k in d:\n",
    "                ans |= dfs(d[cur+k], k)\n",
    "            if cur+k+1 in d:\n",
    "                ans |= dfs(d[cur+k+1], k+1)\n",
    "            return ans\n",
    "        return dfs(1,1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        s_dict = {v: idx for idx, v in enumerate(stones)}\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, k):\n",
    "            # i表示当前的下标，k表示跳刀当前下标跳跃的单位数\n",
    "            if i == len(stones) - 1:\n",
    "                return True\n",
    "            p1 = p2 = p3 = False\n",
    "            if i == 0:\n",
    "                return dfs(1, 1) if stones[0] + 1 == stones[1] else False\n",
    "            # 跳k-1个单位\n",
    "            if k - 1 > 0:\n",
    "                temp_idx = s_dict.get(stones[i] + k - 1)\n",
    "                if temp_idx is not None:\n",
    "                    p1 = dfs(temp_idx, k - 1)\n",
    "            # 跳k个单位\n",
    "            temp_idx = s_dict.get(stones[i] + k)\n",
    "            if temp_idx is not None:\n",
    "                p2 = dfs(temp_idx, k)\n",
    "            # 跳k+1个单位\n",
    "            temp_idx = s_dict.get(stones[i] + k + 1)\n",
    "            if temp_idx is not None:\n",
    "                p3 = dfs(temp_idx, k + 1)\n",
    "            return p1 or p2 or p3\n",
    "        return dfs(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        #dfs\n",
    "        n = len(stones)\n",
    "        self.res = False\n",
    "\n",
    "        # 记忆化搜索！！！\n",
    "        lookup = {}\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, pos, k):\n",
    "            if idx == n-1:\n",
    "                self.res = True\n",
    "                return True\n",
    "            # 不是每次只能向前跳一个，可以隔着跳的\n",
    "            # 第一步只能跳一个单位，只能从0跳到1\n",
    "            for step in [k+1, k, k-1]:\n",
    "                if step >  0 and (pos + step) in stones:\n",
    "                    idx_new = stones.index(pos + step)\n",
    "                    if dfs(idx_new,  pos + step, step):\n",
    "                        break\n",
    "            return False\n",
    "        if stones[n-1] > n*(n-1)/2:\n",
    "            return False\n",
    "        elif stones[n-1] < n:\n",
    "            return True\n",
    "        if not stones or len(stones) < 2 or  stones[1] != 1:\n",
    "            return False\n",
    "        else:\n",
    "            dfs(1,1,1)\n",
    "        return self.res\n",
    "        # 超时了，dfs需要剪枝嘛,服气了，这个应该用动态规划来写，dfs疯狂超时。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        for i in range(1, len(stones)):\n",
    "            if stones[i] - stones[i - 1] > i:\n",
    "                return False\n",
    "        dp = defaultdict(lambda: defaultdict(lambda: False))\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len(stones)):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                gap = stones[i] - stones[j]\n",
    "                if gap > j + 1:\n",
    "                    break\n",
    "                dp[i][gap] = dp[j][gap] or dp[j][gap - 1] or dp[j][gap + 1]\n",
    "                if i == len(stones) - 1 and dp[i][gap]:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        target = stones[-1]\n",
    "        length = len(stones)\n",
    "        if (length > 2 and stones[1] != 1) or target > length * (length - 1) / 2:\n",
    "            return False\n",
    "        stones = set(stones)\n",
    "\n",
    "        @cache\n",
    "        def dfs(pos, k):\n",
    "            if pos == target:\n",
    "                return True\n",
    "            res = False\n",
    "            if pos + k in stones:\n",
    "                res |= dfs(pos + k, k)\n",
    "            if k > 1 and pos + k - 1 in stones:\n",
    "                res |= dfs(pos + k - 1, k - 1)\n",
    "            if pos + k + 1 in stones:\n",
    "                res |= dfs(pos + k + 1, k + 1)\n",
    "            return res\n",
    "    \n",
    "        return dfs(1, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mem = {}\n",
    "\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        def dfs(curpos:int, target:int, presteps:int) -> bool:\n",
    "            if curpos == target:\n",
    "                return True\n",
    "\n",
    "            if (curpos, presteps) in self.mem:\n",
    "                return self.mem[(curpos, presteps)]\n",
    "\n",
    "            try1 = presteps - 1\n",
    "            try2 = presteps\n",
    "            try3 = presteps + 1\n",
    "\n",
    "            flag1 = False\n",
    "            flag2 = False\n",
    "            flag3 = False\n",
    "            \n",
    "            i = curpos + 1\n",
    "            if try1 > 0:\n",
    "                found = False\n",
    "                while i <= target and stones[i] <= stones[curpos] + try1:\n",
    "                    if stones[i] == stones[curpos] + try1:\n",
    "                        found = True\n",
    "                        break\n",
    "                    else:\n",
    "                        i += 1\n",
    "                if found:\n",
    "                    flag1 = dfs(i, target, try1)\n",
    "            \n",
    "            if try2 > 0:\n",
    "                found = False\n",
    "                while i <= target and stones[i] <= stones[curpos] + try2:\n",
    "                    if stones[i] == stones[curpos] + try2:\n",
    "                        found = True\n",
    "                        break\n",
    "                    else:\n",
    "                        i += 1\n",
    "                if found:\n",
    "                    flag2 = dfs(i, target, try2)\n",
    "\n",
    "            if try3 > 0:\n",
    "                found = False\n",
    "                while i <= target and stones[i] <= stones[curpos] + try3:\n",
    "                    if stones[i] == stones[curpos] + try3:\n",
    "                        found = True\n",
    "                        break\n",
    "                    else:\n",
    "                        i += 1\n",
    "                if found:\n",
    "                    flag3 = dfs(i, target, try3)\n",
    "            \n",
    "            self.mem[(curpos, presteps)] = flag1 or flag2 or flag3\n",
    "            return flag1 or flag2 or flag3\n",
    "\n",
    "        return dfs(0, len(stones) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        memo = dict()\n",
    "        \n",
    "        if stones[1] > 1:\n",
    "            return False\n",
    "\n",
    "        def dfs(i, k):\n",
    "            if i == n - 1:\n",
    "                return True\n",
    "            \n",
    "            if (i, k) in memo:\n",
    "                return memo[(i, k)]\n",
    "            \n",
    "            c1 = False\n",
    "            if stones[i] + k - 1 in stones and k - 1 > 0:\n",
    "                c1 = dfs(stones.index(stones[i] + k - 1), k - 1)\n",
    "            \n",
    "            c2 = False\n",
    "            if stones[i] + k in stones:\n",
    "                c2 = dfs(stones.index(stones[i] + k), k)\n",
    "            \n",
    "            c3 = False\n",
    "            if stones[i] + k + 1 in stones:\n",
    "                c3 = dfs(stones.index(stones[i] + k + 1), k + 1)\n",
    "            \n",
    "            memo[(i, k)] = c1 or c2 or c3\n",
    "            return memo[(i, k)]\n",
    "        \n",
    "        return dfs(1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        if stones[1] != 1:\n",
    "            return False\n",
    "        if len(stones) == 2:\n",
    "            return True\n",
    "        path = {}\n",
    "\n",
    "        def cross_recursive(i, k):\n",
    "            # skip k arrived i\n",
    "            key = (i, k)\n",
    "            if key in path:\n",
    "                return path[key]\n",
    "            if i == stones[-1]:\n",
    "                path[key] = True\n",
    "                return path[key]\n",
    "            goal = i+k\n",
    "            path_a = cross_recursive(goal-1, k-1) if k > 1 and goal-1 in stones else False\n",
    "            path_b = cross_recursive(goal, k) if goal in stones else False\n",
    "            path_c = cross_recursive(goal+1, k+1) if goal+1 in stones else False\n",
    "            path[key] = path_a or path_b or path_c\n",
    "            return path[key]\n",
    "\n",
    "        return cross_recursive(1, 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        \n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            res = False\n",
    "            for k in range(-1, 2):\n",
    "                if j + k > 0:\n",
    "                    a = bisect_left(stones, j + k + stones[i])\n",
    "                    if a < n and stones[a] == stones[i] + j + k:\n",
    "                        if a == n - 1:\n",
    "                            return True\n",
    "                        res |= f(a, j+k)\n",
    "            return res\n",
    "        return f(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        n = len(stones)\n",
    "        stone_num_dict = {}\n",
    "        for i in range(n):\n",
    "            stone_num_dict[stones[i]] = i+1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, last_step, stone):\n",
    "            # print(i, last_step, stone)\n",
    "            if stones[i-1] != stone:\n",
    "                return False\n",
    "            if i == n:\n",
    "                return True\n",
    "            if i > n:\n",
    "                return False\n",
    "            # if i == 1:\n",
    "            #     return dfs(2, 1)\n",
    "            result1 = False\n",
    "            if stones[i-1]+last_step+1 in stone_num_dict:\n",
    "                result1 = dfs(stone_num_dict[stones[i-1]+last_step+1], last_step+1, stones[i-1]+last_step+1)\n",
    "            result2 = False\n",
    "            if last_step > 0 and stones[i-1]+last_step in stone_num_dict:\n",
    "                result2 = dfs(stone_num_dict[stones[i-1]+last_step], last_step, stones[i-1]+last_step)\n",
    "            result3 = False\n",
    "            if last_step - 1 > 0 and stones[i-1]+last_step-1 in stone_num_dict:\n",
    "                result3 = dfs(stone_num_dict[stones[i-1]+last_step-1], last_step-1, stones[i-1]+last_step-1)\n",
    "            return result1 or result2 or result3\n",
    "        return dfs(2, 1, 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        hashmap = {}\n",
    "        if stones[1] != 1:\n",
    "            return False\n",
    "        def dfs(i, k):\n",
    "            if i == stones[-1]: return True\n",
    "            if i not in stones or k <= 0:   return False\n",
    "            if (i, k) in hashmap:   return hashmap[(i, k)]\n",
    "            r1, r2, r3 = dfs(i+k-1, k-1), dfs(i+k, k), dfs(i+k+1, k+1)\n",
    "            hashmap[(i, k)] = r1 or r2 or r3\n",
    "            return hashmap[(i, k)]\n",
    "        return dfs(1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canCross(self, stones: List[int]) -> bool:\n",
    "        res = []\n",
    "        @cache\n",
    "        def dfs(n, cur):\n",
    "            if cur == stones[-1]:\n",
    "                res.append(True)\n",
    "                return\n",
    "                \n",
    "            if cur > stones[-1]:\n",
    "                res.append(True)\n",
    "                return\n",
    "            if cur == stones[0]:\n",
    "                if cur + n in stones:\n",
    "                    dfs(n, cur+n)\n",
    "            else:\n",
    "\n",
    "                if cur + n - 1 in stones and (n-1):\n",
    "                    dfs(n-1, cur+n-1)\n",
    "                if cur + n in stones:\n",
    "                    dfs(n, cur+n)\n",
    "                if cur + n + 1 in stones:\n",
    "                    dfs(n+1, cur+n+1)\n",
    "            return\n",
    "        dfs(1, 0)\n",
    "        return True if res else False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
